package 二叉树;
// 利用二叉搜索树的中序遍历为升序序列这一性质，来递归验证。
// 方法一：官方题解 通过限制每个子树中的上下界（lower和upper）来判断，需额外引入常量：math.MinInt64, math.MaxInt64，不推荐，也没必要。

import java.util.*;

// 方法二：双指针比较法（pre和node），参考B站视频题解，不需额外引入常量，而只需通过一个pre指针，在向上回溯的过程中，不断保存之前的节点用于比较。
// 首先【不断向左子树递归】直至最后空节点：left = dfs(node.Left)
// 然后再自底向上【回溯】的过程中，pre每次保存的都是之前上一层栈空间中的根节点，
// 并不断将当前node节点和pre节点的值做比较：if pre != null && node.Val <= pre.Val { return false }
// 当 node = root 时，pre = root.Left，pre的值应永远小于node的值（满足二叉搜索树中，左子节点值 < 根节点值）
// 当 node = root.Right时，pre = root，pre的值应永远小于node的值（满足二叉搜索树中，根节点值 < 右子节点值）
// 保存当前节点node到pre中，用于下层递归中做比较
// 然后不断向右子树递归：right = dfs(node.Right)
// 最后返回：return left && right，判断当前节点的左右子树是否分别是二叉搜索树

// -------------------------------------------------------------------------
// 本题要点：
// 中序遍历为升序序列
// pre指针指向当前节点的前一个节点

// tip:
// 二叉树遍历只需考虑最小存在情况，顺序存储为例
// 空树： [null]
// 只有根节点：[root null null]  
// 只有左子树： [root left null null null null null]
// 只有右子树： [root null right null null null null]
// 左右子树都有： [root left right null null null null]
// -------------------------------------------------------------------------
public class isValidBST {
    // 定义一个二叉搜索树的节点
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 定义一个pre指针
    static TreeNode pre = null;
    // 定义一个isValidBST方法
    public static boolean isValidBSTm(TreeNode root) {
        // 如果根节点为空，返回true
        if(root == null) return true;
        // 递归左子树
        boolean left = isValidBSTm(root.left);
        // 如果pre不为空，并且当前节点值小于等于pre的值，返回false
        // 中序遍历left->root->right，当前为left，pre为null，当前为root，pre为left，当前为right，pre为root
        // 一定存在pre.val < root.val
        if(pre != null && root.val <= pre.val) return false;
        // 更新pre指针
        pre = root;
        // 递归右子树
        boolean right = isValidBSTm(root.right);
        // 返回左右子树的逻辑与
        return left && right;
    }
    // 建树方法
    public static TreeNode buildTree(String[] nodes) {
        // 如果节点为空，返回null
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null"))
            return null;
        
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        // 创建一个队列，用于存储节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 将根节点加入队列
        queue.offer(root);

        // 遍历节点
        int index = 1;
        while(!queue.isEmpty() && index < nodes.length) {
            // 取出队列中的节点
            TreeNode cur = queue.poll();
            // 如果当前节点不为空，则将左子节点加入队列 
            if(index < nodes.length && !nodes[index].equals("null")) {
                // 创建左子节点
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                // 将左子节点加入队列
                queue.offer(cur.left);
            }
            // 索引加1
            index++;
            // 如果当前节点不为空，则将右子节点加入队列
            if(index < nodes.length && !nodes[index].equals("null")) {
                // 创建右子节点
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                // 将右子节点加入队列
                queue.offer(cur.right);
            }
            // 索引加1
            index++;
        }
        // 返回根节点
        return root;
    }
    // 主方法
    public static void main(String[] args) {
        // 输入
        Scanner sc = new Scanner(System.in);
        // 输入节点 以逗号分隔  
        String s = sc.nextLine();
        // 将节点转换为数组
        String[] nodes = s.split(",");
        // 建树
        TreeNode root = buildTree(nodes);
        // 输出结果
        System.out.println(isValidBSTm(root));
        // 关闭Scanner
        sc.close();
    }
}
